#include <cstddef>
#include <exception>
#include <initializer_list>
#include <new>
#include <stdexcept>
#include <type_traits>
#include <utility>

// 值类型
template <typename T> class MyVector {
  // 迭代器类型
  using value_type = T;
  using iterator = std::size_t;
  using size_type = std::size_t;
  using reference = T &;
  using const_reference = const T &;
  using pointer = T *;
  // 底层存储结构
  value_type *m_data = nullptr;
  // 容量
  size_type m_capacity = 0;
  // 已存储元素数量
  size_type m_size = 0;

public:
  // 构造函数
  MyVector() {}

  explicit MyVector(size_type capacity) : m_capacity(capacity), m_size(0) {
    if (m_capacity > 0) {
      m_data = static_cast<T *>(::operator new(sizeof(T) * m_capacity));
    }
  }
  // 列表初始化
  MyVector(std::initializer_list<T> l) {
    this->reserve(l.size());
    for (auto it = l.begin(); it != l.end(); ++it) {
      this->emplace_back(*it);
    }
  }
  // 拷贝构造函数
  MyVector(const MyVector &other)
      : m_size(other.m_size), m_capacity(other.m_capacity) {
    m_data = static_cast<pointer>(
        ::operator new(sizeof(value_type) * this->m_capacity));
    size_type count = 0;
    try {
      for (size_type i = 0; i < m_size; ++i) {
        new (m_data + i) value_type(other.m_data[i]);
        count++;
      }
    } catch (std::exception &e) {
      for (size_type i = 0; i < count; ++i) {
        m_data[i].~value_type();
      }
      operator delete(m_data);
      throw e;
    }
  }
  // 移动构造函数
  MyVector(MyVector &&other) noexcept
      : m_size(other.m_size), m_capacity(other.m_capacity) {
    m_data = other.m_data;
    other.m_size = 0;
    other.m_capacity = 0;
    other.m_data = nullptr;
  }

  // 赋值运算符
  MyVector &operator=(const MyVector &other) noexcept {
    if (&other == this)
      return *this;
    if (other.m_size == 0)
      return *this;
    // 分配新内存
    pointer t_data = static_cast<pointer>(
        ::operator new(sizeof(value_type) * other.m_capacity));
    size_type count = 0;
    try {
      for (size_type i = 0; i < other.m_size; ++i) {
        new (t_data + i) value_type(other.m_data[i]);
        count++;
      }

    } catch (std::exception &e) {
      for (size_type i = 0; i < count; ++i) {
        t_data[i].~value_type();
      }
      ::operator delete(t_data);
      throw e;
    }
    // 释放原始内存
    if (m_size > 0) {
      clear();
      ::operator delete(m_data);
      m_capacity = 0;
    }
    m_size = other.m_size;
    m_capacity = other.m_capacity;
    return *this;
  }

  // 移动赋值运算符
  MyVector &operator=(MyVector &&other) {
    if (&other == this)
      return *this;
    if (m_size > 0) {
      clear();
      ::operator delete(m_data);
      m_capacity = 0;
    }
    m_data = other.m_data;
    m_size = other.m_size;
    m_capacity = other.m_capacity;
    other.m_data = nullptr;
    other.m_size = 0;
    other.m_capacity = 0;
    return *this;
  }

  // 析构函数
  ~MyVector() {
    clear();
    ::operator delete(m_data);
  }
  // 访问第一个元素
  reference front() {
    if (empty())
      throw std::out_of_range("front: vector is empty");
    return m_data[0];
  }

  const_reference front() const {
    if (empty())
      throw std::out_of_range("front: vector is empty");
    return m_data[0];
  } // 访问最后一各元素
  reference back() {
    if (empty())
      throw std::out_of_range("back: vector is empty");
    return m_data[m_size - 1];
  }

  const_reference back() const {
    if (empty())
      throw std::out_of_range("back: vector is empty");
    return m_data[m_size - 1];
  }
  T &operator[](size_type pos) { return m_data[pos]; }
  const T &operator[](size_type pos) const { return m_data[pos]; }
  T &at(size_type pos) {
    if (pos >= m_size)
      throw std::out_of_range("MyVector::at: pos " + std::to_string(pos) +
                              " out of range (size: " + std::to_string(m_size) +
                              ")");
    return m_data[pos];
  }
  const T &at(size_type pos) const {
    if (pos >= m_size)
      throw std::out_of_range("MyVector::at: pos " + std::to_string(pos) +
                              " out of range (size: " + std::to_string(m_size) +
                              ")");
    return m_data[pos];
  }
  // 直接访问底层连续存储
  pointer data() const noexcept { return m_data; }

  bool empty() const noexcept { return m_size == 0; }

  size_type size() const noexcept { return m_size; }

  void reserve(size_type new_cap) {
    if (new_cap > m_capacity) {
      pointer t_data =
          static_cast<pointer>(::operator new(sizeof(value_type) * new_cap));
      if constexpr (std::is_nothrow_move_constructible<T>::value) {
        for (size_type i = 0; i < m_size; ++i) {
          // 调用对象的赋值运算符
          new (t_data + i) value_type(std::move(m_data[i]));
        }
      } else {
        size_type count = 0;
        try {
          for (size_type i = 0; i < m_size; ++i) {
            // 调用对象的赋值运算符
            new (t_data + i) value_type(m_data[i]);
            count++;
          }
        } catch (std::exception &e) {
          for (size_type i = 0; i < count; ++i) {
            t_data[i].~value_type();
          }
          ::operator delete(t_data);
          throw e;
        }
      }
      // 释放之前的内存
      clear();
      ::operator delete(m_data);
      m_data = t_data;
      m_capacity = new_cap;
    }
  }

  // 返回当前已分配内存空间中可容纳的元素数量
  size_type capacity() const noexcept { return m_capacity; }
  // 释放未使用的内存
  void shrink_to_fit() {
    if (m_size == 0) {
      ::operator delete(m_data);
      m_data = nullptr;
      m_capacity = 0;
      return;
    }
    if (m_size == m_capacity)
      return;
    pointer t_data =
        static_cast<pointer>(::operator new(sizeof(value_type) * m_size));
    if constexpr (std::is_nothrow_move_constructible<T>::value) {
      for (size_type i = 0; i < m_size; ++i) {
        new (t_data + i) value_type(std::move(m_data[i]));
      }
    } else {
      size_type count = 0;
      try {
        for (size_type i = 0; i < m_size; ++i) {
          new (t_data + i) value_type(m_data[i]);
          count++;
        }
      } catch (std::exception &e) {
        for (size_type i = 0; i < count; ++i) {
          t_data[i].~value_type();
        }
        ::operator delete(t_data);
        throw e;
      }
    }
    // 清理资源
    clear();
    // 释放内存
    ::operator delete(m_data);
    m_data = t_data;
    m_capacity = m_size;
  }
  // 清除元素
  void clear() {
    if (m_data != nullptr) {
      for (size_t i = 0; i < m_size; ++i) {
        m_data[i].~T();
      }
    }
    m_size = 0;
  }
  // 插入元素
  void insert(iterator pos, const_reference value) {
    if (pos > m_size)
      throw std::out_of_range("insert: pos out of range");
    // 1. 判断剩余空间是否足够, 内存不够进行扩容
    this->capacity_expansion();
    // 2. 移动元素
    if (m_size > pos) {
      for (size_type i = m_size; i > pos; --i) {
        new (m_data + i) value_type(std::move(m_data[i - 1]));
        m_data[i - 1].~value_type();
      }
    }
    new (m_data + pos) value_type(value);
    m_size++;
  }
  // 就地构造元素
  template <typename... Args> void emplace(iterator pos, Args &&...args) {
    if (pos > m_size)
      throw std::out_of_range("emplace: pos out of range");
    this->capacity_expansion();
    if (m_size > pos) {
      for (size_type i = m_size; i > pos; --i) {
        new (m_data + i) value_type(std::move(m_data[i - 1]));
        m_data[i - 1].~value_type();
      }
    }
    new (m_data + pos) value_type(std::forward<Args>(args)...);
    m_size++;
  }
  // 擦除元素
  iterator erase(iterator pos) {
    if (pos >= m_size)
      throw std::out_of_range("erase: pos out of range");
    m_data[pos].~T();
    for (size_type i = pos; i < m_size - 1; ++i) {
      m_data[i] = std::move(m_data[i + 1]);
    }
    m_size--;
    return pos;
  }
  // 添加元素
  void push_back(const T &value) {
    this->capacity_expansion();
    new (m_data + m_size) value_type(value);
    m_size++;
  }

  void push_back(T &&value) {
    this->capacity_expansion();
    new (m_data + m_size) value_type(std::move(value));
    m_size++;
  }
  // 添加元素
  template <class... Args> void emplace_back(Args &&...args) {
    this->capacity_expansion();
    new (m_data + m_size) value_type(std::forward<Args>(args)...);
    m_size++;
  }
  // 移出末元素
  void pop_back() {
    if (m_size > 0) {
      m_data[m_size--].~T();
    } else {
      throw std::out_of_range("pop_back: vector is empty!");
    }
  }
  // 更改存储的元素数量
  void resize(size_type new_size) {
    if (m_size == new_size)
      return;
    if (new_size < m_size) {
      for (size_type i = new_size; i < m_size; ++i) {
        m_data[i].~value_type();
      }
      m_size = new_size;
      return;
    }
    reserve(new_size);
    for (size_type i = m_size; i < new_size; ++i) {
      new (m_data + i) value_type();
    }
    m_size = new_size;
  }

private:
  void capacity_expansion() {

    if (m_size == m_capacity) {
      size_type new_cap = m_capacity ? m_capacity * 2 : 1;
      // 分配内存空间
      pointer t_data =
          static_cast<pointer>(::operator new(sizeof(value_type) * new_cap));
      // 移动元素
      if (m_size > 0) {
        // 有noexcept 类型的移动构造函数
        if constexpr (std::is_nothrow_move_constructible<T>::value) {
          for (size_type i = 0; i < m_size; ++i) {
            new (t_data + i) value_type(std::move(m_data[i]));
          }
        } else {
          size_type count = 0;
          try {
            for (size_type i = 0; i < m_size; ++i) {
              new (t_data + i) value_type(m_data[i]);
              count++;
            }
          } catch (std::exception &e) {
            for (size_type i = 0; i < count; ++i) {
              t_data[i].~value_type();
            }
            ::operator delete(t_data);
            throw e;
          }
        }
      }
      size_type size = m_size;
      clear();
      ::operator delete(m_data);
      m_data = t_data;
      m_capacity = new_cap;
      m_size = size;
    }
  }
};